1. Field of the Invention
The present invention relates to digital computing, and more particularly to an apparatus and method for an incrementor.
2. Description of the Related Art
An often-useful degenerate form of an adder is the incrementor, which adds a value of xe2x80x9c1xe2x80x9d (usually conditionally) to a numeric operand. Incrementors are particularly useful in some address generation situations where sequential addresses must be generated efficiently. Because the incrementor only has one true operand, it is simpler in structure than a full adder, and a 32-bit incrementor can be built in only two logic levels, in contrast to a full adder. (An example of an adder utilizing three logic levels is set forth in co-pending application, U.S. Pat. Ser. No. 09/206,463 entitled xe2x80x9cMethod and Apparatus for 3-stage 32-bit Adder/Subtractor,xe2x80x9d now U.S. Pat. No. 6,269,387, hereinafter referred to as xe2x80x9cthe 3-stage Adder Application.xe2x80x9d
Traditional Binary Addition
In most computer systems, addition and subtraction of numbers is supported. In systems using traditional binary logic, the truth table for one-bit addition is set forth in Table 1.
In the last row of Table 1, a carry condition occurs. That is, the result is 0, but a carry into the next-higher-order bit position, corresponding to a decimal value of 2, has conceptually occurred.
In addition to single bits, the addition operation may be performed on multiple bits, including addition of two two-bit values. The truth table for such an operation is set forth in Table 2, where the first operand A is a two-bit value comprising bits A0 and A1. The second operand, B, is a two-bit value comprising bits B0 and B1.
Each output value in the xe2x80x9cA+Bxe2x80x9d column of Table 2 indicated with an asterisk denotes a carry condition where a one has conceptually carried into the next-higher-order bit (the bit position corresponding to a decimal value of four).
N-nary Logic
The present invention utilizes N-nary logic. The N-nary logic family supports a variety of signal encodings, including 1-of-4. The N-nary logic family is described in a copending patent application, U.S. patent application Ser. No. 09/019,355, filed Feb. 5, 1998, now U.S. Pat. No. 6,066,965, and titled xe2x80x9cMethod and Apparatus for a N-Nary logic Circuit Using 1-of-4 Signalsxe2x80x9d, which is incorporated herein for all purposes and hereinafter referred to as xe2x80x9cThe N-nary Patent.xe2x80x9d In 1-of-4 encoding, four wires are used to indicate one of four possible values. In contrast, traditional static design uses two wires to indicate four values, as is demonstrated in Table 2. In Table 2, the A0 and A1 wires are used to indicate the four possible values for operand A: 00, 01, 10, and 11. The two B wires are similarly used to indicate the same four possible values for operand B. xe2x80x9cTraditionalxe2x80x9d dual-rail dynamic logic also uses four wires to represent two bits, but the dual-rail scheme always requires two wires to be asserted. In contrast, N-nary logic only requires assertion of one wire. The benefits of N-nary logic over dual-rail logic, such as reduced power and reduced noise, should be apparent from a reading of The N-nary Patent.
All signals in N-nary logic, including 1-of-4, are of the 1-of-N form where N is any integer greater than one. A 1-of-4 signal requires four wires to encode four values (0-3 inclusive), or the equivalent of two bits of information. More than one wire will never be asserted for a 1-of-N signal. Similarly, N-nary logic requires that a high voltage be asserted for all values, even 0.
Any one N-nary gate may comprise multiple inputs and/or outputs. In such a case, a variety of different N-nary encodings may be employed. For instance, consider a gate that comprises two inputs and two outputs, where the inputs are a 1-of-4 signal and a 1-of-2 signal and the outputs comprise a 1-of-4 signal and a 1-of-3 signal. Various variables, including P, Q, R, and S, may be used to describe the encoding for these inputs and outputs. One may say that one input comprises 1-of-P encoding and the other comprises 1-of-Q encoding, wherein P equals two and Q equals four. Similarly, the variables R and S may be used to describe the outputs. One might say that one output comprises 1-of-R encoding and the other output comprises 1-of-S encoding, wherein R equals four and S equals 3. Through the use of these, and other, additional variables, it is possible to describe multiple N-nary signals that comprise a variety of different encodings.
The preferred embodiment of the present invention comprises a two-stage 32-bit incrementor that receives as inputs a 32-bit 1-of-4 operand to be incremented and a 1-of-2 increment control select signal. In the first level of logic, the value of each dit of the operand is both stored in a buffer and is also incremented. Also in the first level, an HPG carry propagate signal is also generated for each block of four dits. Both the buffered value and the incremented value for each dit are passed to the second level of logic, along with the block HPG signals. In the second level of logic, the block HPG signals are used to determine whether the original buffered value or the incremented value of each dit should be output from the incrementor. The preferred embodiment of the incrementor also produces, in addition to an incremented 1-of-4 32-dit output operand, a 1-of-2 carry out indicator.